昨天介紹完了動態規劃的基礎，知易行難，今天會挑幾題一起來看看動態規劃的解題邏輯。
其中最難的地方莫過於挑出正確的狀態轉移方程式，賦予 dp[i] 正確的意義。
有些題目確實第一次初見要能快速的想出方程式並不容易，這個部分只能靠多做題目來增加題感，部分題目則是有規律，狀態轉移方程式中也有常見的幾種，看到部分關鍵字會讓我們有些嘗試的頭緒。
這邊我再把昨天列出的邏輯步驟貼過來，接著就來看題目吧。

1. 我們需要先定義問題中核心要求的數、相關變化參數 - 確認狀態
2. 了解該問題的關聯(遞增 / 遞減，挑選的邏輯) - 確認選擇(邏輯)
3. 透過 1 與 2 的分析，去推出狀態轉移方程式，決定目標狀態如何被推導出來、下標涵義
4. 狀態推導公式一般會需要基礎狀態才能夠開始不斷推導，確立初始值(如上面的狀態，)
5. 確認於連續事件中狀態轉移方程式對資料源的遍歷方向(從前往後、從後往前、矩陣上到下...等等)
6. 驗證推導結果，確定初始值

Unique Paths II

這題有個基本版的，可以先試試。
挑這題的原因是，這題的輸入是矩陣，我們可以看看在矩陣中的狀態轉移方程式會有什麼樣的不一樣。

題目是這樣的，我們有一個 m * n 的棋盤，一個機器人，會從棋盤左上角出發，目標是右下角。機器人每次可以選擇往右走或往下走，也只有這兩個選擇。
給予的矩陣中，0 代表空格，1 障礙物，如果有障礙物，機器人無法移動到該格。
題目要求回傳機器人從起點走到終點(右下角)，共有幾種不同的走法。
基本版是沒有障礙物的版本，老實說其實也差不多。

我們關注的狀態是走到右下角該格的走法。
能做的選擇是機器人要往右走還往下走，同一格每一次分叉，如果右和下都能走，則走法會變多，如果只有一方向能走，則走法數量維持不變。
因為我們關注的是走法，目標求走到右下角，通常會回推想想看走到右下角的走法和走到其他格的走法有無關聯。
從第二點關注選擇時得到的觀點，推敲後應該能發現走到右下角那格的走法，應該是由走到右下角正上方和走到右下角左方的走法數相加得到。反推這個規律應該能套用到所有格子：某格的走法應該等於走到該格的上方的走法數加上走到該格左方的走法數。
如果左方或上方為障礙物或邊界，則沒有辦法可以走到該格，標示為 0。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
dp 的定義是走到該格的走法數量，dp[i][j] 就是走到 i,j 格的走法數量。
討論邊界和障礙物的那句話其實就包含了初始值相關的設定：超出邊界的話該方向以 0 計算。
初始 dp[0][0] 應該被定義為 1，從 0,0 走到 0,0 有 1 種走法 ─ 但這邊要注意一個 case 是如果 0,0 的位置上有障礙物，雖然題目說的可能有點曖昧，但這個情況丟測資讓它測可以知道這個情況會導致走法為 0，是特例要另外處理。
遍歷方向我們就正常的由左至右、由上至下的遍歷棋盤矩陣就可以了，我們的當前格子 dp 來源為左和上，由左至右由上至下的這個順序可以保證遍歷到該格是 dp 計算所需的格子都已經處理過。
最後可以驗證一下像剛剛題到的 0,0 是障礙物的 case、題目基本測資，如果按照上面邏輯處理，那應該是沒問題。

程式碼如下

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        
        var dp  = new int[obstacleGrid.Length][];
        for(var i = 0; i < obstacleGrid.Length; i++){
            dp[i] = new int[obstacleGrid[0].Length];
            for(var j = 0; j < obstacleGrid[0].Length; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
                else if(i == 0){
                    dp[i][j] = j == 0 ? obstacleGrid[0][0] == 1 ? 0 : 1 : dp[i][j - 1] == 0 ? 0 : 1;
                }
                else if(j == 0){
                    dp[i][j] = i == 0 ? obstacleGrid[0][0] == 1 ? 0 : 1 : dp[i - 1][j] == 0 ? 0 : 1;
                }
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[^1][^1];
    }
}

像矩陣類型的遍歷，雙迴圈的時候可以想一下行和列遍歷第0行 / 列的時候，通常會是相對特異值要處理，如這題就是以 0 當作不存在位置(超出邊界)的數值。
另外這題也可以略瞥見一些遍歷方向對動態規劃的重要性，基本上就是狀態轉移方程式列出來後，要保證計算到值時所需的狀態 / 參數都是已經被處理過的，如這題的左和上格。儘管我們直覺可能就會寫左到右上到下，但有意識地去知道這樣寫正好能符合狀態轉移方程式所需、對這樣的方程式該這樣寫，也是很重要的意識。

Longest Increasing Subsequence

給予一個整數陣列，回傳該陣列中最長嚴格遞增的子序列長度。
嚴格遞增指的是必須遞增，如 1,2,3，像 2,3,3 因為 3 - 3 並沒有遞增，就不符定義。
序列指的是取出不一定連續、但和來源陣列順序一樣的數個數構成，如來源陣列為 [1,2,4,3,4]，則其中我們可以忽略第 3 個元素的 4，得到這樣的子序列 [1,2,3,4]，所以對這個來源陣列而言，我們得到的最長遞增子序列長度為 4。

首先是狀態，我們關注的是遍歷整個陣列的長度後，找出其中最長嚴格遞增的子序列長度。
可以想見，要找到最長的，我們得知道所有子序列的嚴格遞增長度，才能比較最長的。
這題倒沒有什麼選擇，就是不符合嚴格遞增的狀況下，就不能被選為子序列的成員。
這裡有個當題目與子序列有關的時候的 Hint，或是說小 Tips：可以嘗試把 dp[i] 的定義定成以 i 為開頭的子序列，然後跟狀態關聯上，以這題就是把 dp[i] 定義為以 i 為開頭的最長嚴格遞增子序列的長度。
如此當我們完整建構了 dp 後，我們就能從所有的嚴格遞增子序列中挑出最長的一個做為本題答案。
接著是遞增子序列怎麼建構呢？
可以想見如果第 i 個元素大於第 j 個元素(j < i)，則可以在 j 元素後面串上 i 讓遞增子序列的長度加 1，我們會由前往後遍歷、建構這個 dp 陣列，以 j 為遍歷變數(iterate variable)，i 為當前遍歷到的元素，則我們的 dp 可以定義為(在 j < i 且 nums[j] < nums[i] 的情況下)：
dp[i] = Math.Max(1 + dp[j], dp[i])
j 會遍歷第 0 個到第 i - 1 個元素，dp[i] 初始為 0，會持續和遍歷項比較並更新為大的結果，這邊的 1 + dp[j]，dp[j] 代表的是在遍歷到 i 之前的以 j 為開頭的遞增子序列長度，1 表示取用了 i 這個元素到以 j 開頭的子序列中(因為 j < i 且 nums[j] < nums[i]，符合定義)。
初始值則是把 dp 陣列中每個值都設為 1(每個人至少有自己一個人的長度 1)。
最後針對這樣的程式嘗試印幾個結果出來，確認能符合題目的範例輸入，至此題目結束。

程式碼如下

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var dp = new int[nums.Length];
        Array.Fill(dp, 1);
        for(var i = 0; i < nums.Length; i++)
        {
            for(var j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = Math.Max(dp[i], 1 + dp[j]);
                }
            }
        }

        return dp.Max();
    }
}

狀態轉移方程式的推導除去經驗外，就是會有向這題這種關鍵字(子序列)、上題那樣大問題可拆分為重複子問題比較明顯的例子，那些初次難以處理 / 牽涉到比較多數學理論的題目先方一旁，總之先讓這類能把握住的好好抓住題目中的線索，好好把握吧。

明天會往一些動態轉移方程式思維更不同的題目去討論，在有限的題目數中盡量了解一下不同的轉移方程式切入點。